package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 描述:131. 分割回文串
 *
 * @author Madison You
 * @created 20:41
 */
public class Mid_131_Partition {
    public static void main(String[] args) {
        new Mid_131_Partition().partition("aab");
    }

    List<List<String>> list = new ArrayList<>();

    List<String> temp = new ArrayList<>();

    public List<List<String>> partition(String s) {
        back(s, 0);
        return list;
    }

    public void back(String s,int index) {
        if (index == s.length()) {
            list.add(new ArrayList<>(temp));
            return;
        }
        for(int i = index ; i < s.length() ; i ++) {
            if (check(s,index,i)) {
                String str = s.substring(index,i + 1);
                temp.add(str);
            } else {
                continue;
            }
            back(s,i + 1);
            temp.remove(temp.size() - 1);
        }
    }

    private boolean check(String s,int index,int i) {
        while(index < i) {
            if (s.charAt(index) == s.charAt(i)) {
                index ++;
                i--;
            } else{
                return false;
            }
        }
        return true;
    }
}
